1. Field of the Invention
The present invention generally relates to imperceptible watermarking of images, and more particularly to a digital watermarking method that performs positive identification of customers who purchase and publish images.
2. Background Description
An imperceptible watermark is defined as an alteration of a data set which is, for the most part, imperceptible to a human i.e., the watermark should be invisible or almost invisible, but can be recognized by a machine such as a computer. The general principle of developing a watermark is disclosed, for example, by M. M. Yeung et al. in xe2x80x9cDigital Watermarking for High-Quality Imagingxe2x80x9d, Proceedings of the IEEE Signal Processing Multimedia Workshop, Princeton, N.J. (1997).
A robust watermark is one conceived to survive modifications of the image, and more precisely, to still be detectable when the image has been modified to some reasonable extent. Robust watermarks are usually required to be non-removable by an adverse party, at least not removable without visible distortion to the image. They are usually designed, for instance, to establish ownership or to help protect copyrights. In several cases, one expects them to be detectable when the image is transferred to the analog world, such as when printed or transformed into analog signals such as required for display on a TV screen.
Watermarks cannot be replaced by digital signatures in this context, as known signature schemes with no visible trace on the image do not resist transfer from the digital to analog world. Because of the dual constraint of invisibility and resistance to minor changes in the image, robust watermark detection is therefore based on statistical analysis: any individual components of a mark can be altered by attack and/or by digital/analog (or D/A) conversion so that one is reduced to check that traces of the overall mark persist.
In general, a robust watermark consists of an array M(K) of elements, M(K)(h,v) defined by a cryptographically designed key K. Here, h and v stand respectively for horizontal and vertical coordinates. According to one technique for generating a robust watermark, M(K) is a matrix of xe2x80x9c0""sxe2x80x9d and xe2x80x9c1""sxe2x80x9d, where a zero means a pixel gets brighter, and a 1 in the matrix means a pixel gets darker after watermarking (one can have a richer set of possibilities where, for instance, a xe2x80x9c2xe2x80x9d in the matrix means that no change is made.) The watermark M(K) (referred to as a xe2x80x9cmaskxe2x80x9d) is used to modify some pixels attributes according to some algorithm, defining some function F, which generates the modified pixel attribute m(h,v) at location (h,v) as a function of the mask M, the pixel""s attribute before marking A(h,v), and the attributes before marking An(h,v) of neighboring pixels, i.e.,
m(h,v)=F(M(K)(h,v), A(h,v), An(h,v)).
The amount by which watermarking modifies the luminosity at a given pixel is not necessarily uniform for better visual performance and/or for better resistance to attacks. Because the image and the accompanying watermark are expected to suffer some modifications, the key K, as well as the function F, are usually chosen as secret keys: a description of cryptographic techniques, with directions on how to use several of their implementations, can be found in Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone, CRC Press, 1997.
An example of robust invisible robust watermark has been disclosed, for instance, in U.S. Pat. No. 5,825,892 issued to Mintzer and Braudaway.
An aim of the present invention is to address the following business case. Suppose an image vendor (whom we will call The Ven Company in this hypothetical) sells digital images to a pool of customers C1,C2, . . . , CN. In fact not all images are necessarily sold to all customers. Each customer indeed only buys the right to print these images in some publications. No customer has the right to circulate or sell digital form of the images.
The Ven Company wants to prevent unauthorized resale of these images. In particular, if one of the images is found in some publication not listed by any customer, The Ven Company will legitimately suspect that one of its customers has broken his contract. It would therefore be advantageous for The Ven Company to identify the customer in its pool which has acted in this way, so that The Ven Company can pursue legal remedies including suing the customer for injunctive relief to prevent the unauthorized publication and/or damages, terminate its business relationship with this customer, or both.
In principle, this problem may be addressed using a robust invisible watermark scheme as defined above. However, given an image carrying a watermark, Wi, belonging to a large collection W1, W2, . . . , Wm, recognizing which one of these marks has been used, if any, is difficult and time consuming. To segregate among different customers, the number, m, of watermarks needs to be as large as the maximum number of customers that The Ven Company expects for its best selling digital images, Also, because of the statistical nature of robust watermark detection, detection can be unreliable for large m, and careless use of watermarks could lead to a false positive identification, leading to potentially embarrassing problems with non-offending customers. On the other hand, the problem of a false negative is, in principle, solved by the intrinsic qualities of the watermarking scheme used, and therefore reduces the problem To selecting which mark is used out of a large collection.
A well knows kind of attack on watermarks in a situation as described above is collusion of several customers. This can be described as follows: assume customers Ci1, Ci2, . . . , Cin all buy the same image I, which has been watermarked with different marks Wi1, Wi2, . . . , Win, so that they receive image files Ii1, Ii2, . . . , Iin, respectively. These customers can together create a new image file Ic (where c stands for collusion) where each pixel (h,v) is defined by a combination of averaging and random choices among the (h,v) pixels of all images Ii1, Ii2, . . . , Iin. It has been recognized that arbitrary collusions will defeat watermarking. Prior work can be found on protection against collusion attacks, such as xe2x80x9cCollusion secure fingerprinting for digital dataxe2x80x9d by D. Boneh, and J. Shaw, IEEE Transactions on Information Theory, Vol 44, No. 5, pp. 1897-1905,(1998).
It is an object of the present invention to provide an improved method for encoding a watermark into a digital image, so that a person who engaged in an unauthorized use of th digital image may be identified with greater accuracy compared with conventional methods.
It is another object of the present invention to provide an improved method for detecting when an unauthorized digital image has been formed as a result of collusion between or among cuts of a digital image vendor, and then to identify the colluding parties with greater accuracy compared with conventional methods.
It is another object of the present invention to provide a method of the aforementioned types which significantly reduces the number of processing steps required to determine the customer or customers who engaged in an unauthorized use of a digital image.
It is a further object of the present invention to provide a method for performing collusion detection based on an analysis of several images sold to one or more customers.
These and other objects of the invention are achieved by providing a digital watermarking method which encodes two watermarks, or masks, into a digital image offered for use by a vendor. The method may advantageously be applied for watermark detection alone, or may also be used to perform collusion detection among two or more customers. The type of watermarks and the manner in which the watermarks are encoded are determined accordingly.
In accordance wit a first embodiment of the method for performing watermark detection, first and second collections of masks are formed, a from each collection is chosen to form a pair of masks, and the pair of masks are then encoded into the digital image. Next, a digital image suspected of being an unauthorized version of the encoded digital image is obtained. The suspected image is then compared with the masks in the first and second collections on a mask-by-mask basis. If the first and second masks of the pair are found in the image, the customer who distributed the unauthorized version of the encoded digital image may easily be determined, since each pair of masks has beforehand been assigned to one and only one customer. The masks in the first and second collections may be formed according to a random process. Further, in order to prevent a false positive, the masks in the first and second collections must be different as determined by a predetermined criteria, e.g., at least one third of the values in each mask must be different from the values in the other masks.
In order to reduce the number of comparisons required to detect the watermarks in a suspected unauthorized image, the number of masks in both collections are preferably the same. As a result, the present method performs recognition among N customers while performing at most 2{square root over (N)} tests for the case when there is no collusion, and recognizes frequent collusions of two or more customers. (For purposes of this invention, {square root over (X)} stands for smallest integer larger or equal to The square root of X).
According to a second embodiment of the present invention applied for collusion detection, first and second collections of masks are formed each including a sub-collection of masks of a first type and a sub-collection of masks of a second type. A plurality of pairs of masks are then assigned to each of a plurality of customers, with each pair of masks assigned per customer corresponds to a different one of a plurality of digital images Ij offered for use by the vendor. The first mask in each pair is derived from the first collection and the second mask is derived from the second collection, with the first mask and the second mask either both being the first type or both being of the second type. The pair of masks is then encoded into a digital image authorized for use by the associated customer.
The first and second collections of masks are formed in accordance with steps that include: a) defining at least one initial mask in a temporary collection, b) choosing a plurality of patterns for the digital images, each of the patterns chosen for a subset of pixels in a respective one of the digital images, c) generating a first tentative mask as a possible mask to be added to the temporary collection; d) modifying the first tentative mask to carry one of said patterns Pat(j) for a subset Sj of pixels (h,v) within digital image Ij, e) generating a second tentative mask which is the same as the first tentative mask except that the second tentative mask carries a pattern which is an inversion Patxe2x80x2(j) of the pattern Pat(j) carried by the first tentative mask, f) comparing the first tentative mask and the second tentative mask to the masks already in the temporary collection, g) rejecting the first tentative mask and The second tentative mask if a predetermined correspondence exists between at least one of the first tentative mask and the second tentative mask and any of the masks in the temporary collection, and h) adding the first tentative mask and the second tentative mask to the temporary collection if the predetermined correspondence does not exist between both the first tentative mask and the second tentative mask and any of the masks in the temporary collection.
Steps c)-h) are then repeated until a desired number of masks are included in the temporary collection. The temporary collection is then divided into two groups corresponding, respectively, to the first collection and the second collection, where the sub-collection of the first type in the first collection and the second collection includes masks which carry patterns Pat(j) and the sub-collection of the second type includes masks which carry patterns Patxe2x80x2(j).
To determine the customers who colluded to form the suspected unauthorized image, one of the following symbolic sequences s1(j,Ci) for each of the vendor""s customers:
s1(j, Ci)=0 if Ci has not bought image Ij,
s1(j, Ci)=1 if Image Ij sold to Ci has watermarks of type A,
s1(j, Ci)=2 if Image Ij sold to Ci has watermarks of type B.
An output Sj is then computed for all possible pairs of customers based on the symbolic sequences. The output Sj for all possible pairs of customers are then compared to the suspected image, and the partes who colluded are determined based on an outcome of the comparing step.
Another embodiment of the present method for performing collusion detection is similar to the foregoing embodiment except that instead of using sub-collections, masks are formed for respective customers. Each mask (M) corresponds to a two-dimensional concatenation of two smaller masks. The second smaller mask (Msxe2x80x2) is an inversion of the first smaller mask (Ms). Further, a correlation is drawn between the first mask and a first letter of an alphabet, as well as between the second mask and a second letter of the alphabet. Mask (M) is then regarded as a code word written in the first and second letters.
According to another embodiment of the present method for performing watermark detection based on more than one image, n collections of watermarks are formed, a set of a watermarks W(i) are assigned to each customer with the n watermarks being chosen from the n collections of watermarks, respectively, a different one of the watermarks from the set W(i) is encoded into respective images, and the images are sold to a single customer. A group of images suspected of being unauthorized versions of the images used by the customer are then obtained, a predetermined number in the group are analyzed, and the group of images is identified as being derived from the customer when watermarks are found in the predetermined number of images in the group.
According to another embodiment of the present method for performing collusion detection, n collections of watermarks are formed, watermarks are randomly chosen from the n collections, and the randomly chosen watermarks are encoded into respective ones of a plurality of images. At least two customers are then authorized to use the images, with at least a portion of the images being encoded with a common watermark. A group of suspected images is then obtained, analyzed to determine which images in the group have the common watermark, and parties to the collusion are determined based on the images containing the common watermark.
Further, any of the methods of the present invention may advantageously be embodied in a computer program adapted for execution on either a general purpose or special purpose computer.